package com.njupt.graphTheory;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/7 11:19
 * @Description: 130. 被围绕的区域
 * @Version: 1.0
 */


public class Solve_130 {

    public static final int DIR[][] = {{0,1},{1,0},{-1,0},{0,-1}};

    class Point{
        int x;
        int y;
        Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] isVisited = new boolean[m][n];
        Deque<Point> queue = new LinkedList<>();

        //1、遍历邻接矩阵，找到第一个为o的节点v
        for (int i = 0; i < m; i++) {
            if(board[i][0] == 'O'){
                queue.addLast(new Point(i,0));
                board[i][0] = 'T';
            }
            if(board[i][n-1] == 'O'){
                queue.addLast(new Point(i,n-1));
                board[i][n-1] = 'T';
            }
        }

        for (int j = 1; j < n-1; j++) {
            if(board[0][j] == 'O'){
                queue.addLast(new Point(0,j));
                board[0][j] = 'T';
            }
            if(board[m-1][j] == 'O'){
                queue.addLast(new Point(m-1,j));
                board[m-1][j] = 'T';

            }
        }

        //广度优先遍历
        bfs(board,queue);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j <n ; j++) {
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                } else if (board[i][j] == 'T') {
                    board[i][j] = 'O';
                }
            }

        }
    }



    private void bfs(char[][] board, Deque<Point> queue) {

        while(!queue.isEmpty()){
            //1、从队列中取出当节点v
            Point point = queue.pollFirst();
            int curX = point.x;
            int curY = point.y;
            //2、对该节点v进行广度优先遍历
            for (int[] ints : DIR) {
                int nextX = ints[0] + curX;
                int nextY = ints[1] + curY;
                if(nextX >= 0 && nextX < board.length && nextY >= 0 && nextY < board[0].length
                        && board[nextX][nextY] == 'O'){

                    board[nextX][nextY] = 'T';
                    queue.addLast(new Point(nextX,nextY));
                }


            }
        }
    }

    public static void main(String[] args) {
//        char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        char[][] board = {{'O','O','O','O'},{'O','O','O','O'},{'O','O','O','O'}};
//        char[][] board = {{'X'},{'X'},{'O'},{'X'}};
//        char[][] board = {{'X','X','O','X'}};
        Solve_130 test = new Solve_130();
        test.solve(board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}
